次のプログラムの説明及びプログラムを読んで，設問１～３に答えよ。
〔プログラムの説明〕
関数 BMMatch は，Boyer-Moore-Horspool 法（以下，BM 法という）を用いて， 文字列検索を行うプログラムである。BM 法は，検索文字列の末尾の文字から先頭に 向かって，検索対象の文字列（以下，対象文字列）と１文字ずつ順に比較していくことで照合を行う。 比較した文字が一致せず，照合が失敗した際には，検索文字列中の文字の情報を利用して， 次に照合を開始する対象文字列の位置を決定する。このようにして明らかに不一致となる照合を省き， 高速に検索できる特徴がある。
(1) 対象文字列を Text[]，検索文字列を Pat[] とする。ここで，配列の添字は１から始まり， 文字列 Text[] の i 番目の文字は Text[i] と表記される。Pat[] についても同様に i 番目の 文字は Pat[i] と表記される。また，対象文字列と検索文字列は，英大文字から構成される。
例えば，対象文字列 Text[] が“ACBBMACABABC”，検索文字列 Pat[] が“ACAB”の場合の例を図１に示す。
図１ 対象文字列と検索文字列の格納例
(2) 関数 BMMatch では，照合が失敗すると，次に照合を開始する位置まで検索文字列を移動するが， その移動量を格納した要素数 26 の配列 Skip[] をあらかじめ作成しておく。 Skip[1] に文字“A”に対応する移動量を，Skip[2] に文字“B”に対応する移動量を格納する。 このように，Skip[1] ～ Skip[26] に文字“A”～“Z”に対応する移動量を格納する。 ここで，検索文字列の長さを PatLen とすると，移動量は次のようになる。
② 検索文字列の Pat[1] から Pat[PatLen－１] に現れる文字に対応する移動量は， その文字が，検索文字列の末尾から何文字目に現れるかを数えた文字数から１を引いた値とする。 ただし，複数回現れる場合は，最も末尾に近い文字に対応する移動量とする。
② 文字“B”は検索文字列の末尾の文字にだけ現れるので，移動量は PatLen（＝４）となる。
③ 文字“C”は検索文字列の末尾から３文字目（Pat[2]）に現れるので，移動量は２（＝３－１）となる。
④ “A”，“B”及び“C”以外の文字については検索文字列に現れないので，移動量は PatLen（＝４）となる。
図２ 図１の格納例における Skip[] の値
(4) 図１の例で照合する場合の手順は，次の①～⑨となり，その流れを図３に示す。 この例では，PatLen＝4 なので，検索文字列の末尾の文字は Pat[4] である。
図３ 図１の場合の照合手順
② Text[3] と Pat[3] を比較する。Text[3] の“B”と Pat[3] の“A”は異なる文字である。
③ ①で検索文字列の末尾の文字 Pat[4] と比較した Text[4] を基準に， Text[4] の文字“B”に対応する移動量である Skip[2] の値４だけ Pat[] を右側に移動し， Text[8] と Pat[4] の比較に移る。
④ Text[8] と Pat[4] を比較する。Text[8] の“A”と Pat[4] の“B”は異なる文字である。
⑤ ④で検索文字列の末尾の文字 Pat[4] と比較した Text[8] を基準に，Text[8] の文字“A”に 対応する移動量である Skip[1] の値 1 だけ Pat[] を右側に移動し，Text[9] と Pat[4] の比較に移る。
⑥ Text[9] と Pat[4] を比較する。Text[9] と Pat[4] は同じ文字“B”である。
⑦ Text[8] と Pat[3] を比較する。Text[8] と Pat[3] は同じ文字“A”である。
⑧ Text[7] と Pat[2] を比較する。Text[7] と Pat[2] は同じ文字“C”である。
⑨ Text[6] と Pat[1] を比較する。Text[6] と Pat[1] は同じ文字“A”である。
⑥～⑨の比較で，対象文字列 Text[] の連続した一部分が検索文字列 Pat[] に完全に一致したので， 検索は終了する。
〔関数 BMMatch の引数と返却値〕
関数 BMMatch の引数と返却値の仕様は，次のとおりである。
関数 BMMatch では，次の関数 Index を使用する。
〔関数 Index の仕様〕
引数にアルファベット順で n 番目の英大文字を与えると，整数 n（１≦ n ≦ 26 ）を返却値とする。
〔プログラム〕
設問１ プログラム中の 
に入れる正しい答えを，解答群の中から選べ。
a，b に関する解答群
| ア Ø | イ 1 | ウ I － PatLen |
| エ PatLen | オ PatLen － 1 | カ PatLen － I |
設問２ 次の記述中の に入れる正しい答えを，解答群の中から選べ。
図４のように，Text[]に“ABCXBBACABACADEC”，TextLen に 16，Pat[] に “ABAC”， PatLen に 4 を格納し，BMMatch(Text[]，TextLen，Pat[]，PatLen）を呼び出した。 プログラムが終了するまでにαは
回実行され，
βは 
回実行される。
またこの場合，関数 BMMatch の返却値は 
である。
図４ 対象文字列と検索文字列
c～e に関する解答群
| ア 3 | イ 4 | ウ 5 | エ 6 | オ 7 |
| カ 8 | キ 9 | ク 10 | ケ 11 | コ 12 |
| 設問３ |
次の記述中の に入れる正しい答えを，解答群の中から選べ。
ここで，プログラム中の  と
 には正しい答えが入っているものとする。
|
f に関する解答群
イ 対象文字列中に，検索文字列が含まれているのに，－１を返す場合がある
ウ 正しい値を返す
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
